package demo9;

/**
 * 替换后的最长重复字符串
 * 给你一个仅由大写英文字母组成的字符串，
 * 你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。
 * 在执行上述操作后，找到包含重复字母的最长子串的长度。
 */
public class Main6 {
    public static void main(String[] args) {
        System.out.println(characterReplacement("AABAABAA",1));
    }

    public static int characterReplacement(String s, int k) {
        if(s==null) return 0;
        int[] map = new int[26];
        char[] a = s.toCharArray();
        int left = 0;
        int right;
        int maxCount  = 0;   // 窗口内出现次数最多的字符的出现次数
        int res = 0;
        // right一直向右扩充
        for (right = 0; right < a.length; right++) {
            map[a[right]-'A']++;
            // 每扩充一格 就重新计算maxCount
            maxCount = Math.max(maxCount,map[a[right]-'A']);

            // 重复字符可以填满整个窗口,更新结果。
            if(right-left+1-maxCount<=k){
                res = Math.max(res,right-left+1);
            }else{
                // 窗口大小 减去 重复字符出现次数>k ，说明重复字符不能填满整个窗口
                map[a[left]-'A']--;
                left++;
            }
        }
        return res;
    }
}
